from typing import List


class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]

        adjs = [set() for _ in range(n)]
        for u, v in edges:
            adjs[u].add(v)
            adjs[v].add(u)

        leaves = [u for u in range(n) if len(adjs[u]) == 1]
        while True:
            if len(leaves) == 1 or (len(leaves) == 2 and (leaves[0] in adjs[leaves[1]])):
                return leaves

            new_leaves = []
            for u in leaves:
                assert len(adjs[u]) == 1
                v = next(iter(adjs[u]))
                adjs[u].remove(v)
                adjs[v].remove(u)
                if len(adjs[v]) == 1:
                    new_leaves.append(v)

            leaves = new_leaves


class Solution2:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        from collections import deque
        adjs = [[] for _ in range(n)]
        for u, v in edges:
            adjs[u].append(v)
            adjs[v].append(u)
        S = {u for u in range(n) if len(adjs[u]) <= 1}
        q = deque(S)
        popped = []
        while q:
            if len(q) == 1:
                print('popped:', popped)
                return list(q)
            elif len(q) == 2 and q[0] in adjs[q[1]] and q[1] in adjs[q[0]]:
                print('popped:', popped)
                return list(q)

            u = q.popleft()
            popped.append(u)
            assert len(adjs[u]) == 1

            v = next(iter(adjs[u]))
            adjs[v].remove(u)
            adjs[u].remove(v)
            if len(adjs[v]) <= 1:
                q.append(v)

from collections import deque
class SolutionBrutal:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        adjs = [[] for _ in range(n)]
        for u, v in edges:
            adjs[u].append(v)
            adjs[v].append(u)

        def bfs(s):
            INF = n
            d = [INF] * n
            d[s] = 0
            q = deque([s])
            while q:
                u = q.popleft()
                for v in adjs[u]:
                    if d[v] == INF:
                        d[v] = d[u] + 1
                        q.append(v)
            return d

        heights = []
        for s in range(n):
            d = bfs(s)
            heights.append(max(d))
        minHeight = min(heights)
        return [i for i, x in enumerate(heights) if x == minHeight]


class SolutionBFS:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        INF = 10**10
        def bfs(n, adj, s, t=None):
            d = [INF] * n
            d[s] = 0
            p = [None] * n
            q = deque()
            q.append(s)
            while q:
                u = q.popleft()
                if u == t:
                    return d
                for v in adj[u]:
                    if d[v] == INF:
                        d[v] = d[u] + 1
                        p[v] = u
                        q.append(v)
            return d, p
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        d1, _ = bfs(n, adj, 0)
        u = max(range(n), key=lambda u: d1[u])
        d2, p = bfs(n, adj, u)
        v = max(range(n), key=lambda u: d2[u])
        path = []
        while v is not None:
            path.append(v)
            v = p[v]
        if len(path) % 2 == 0:
            return [path[len(path) // 2 - 1], path[len(path) // 2]]
        else:
            return [path[len(path) // 2]]


solution = SolutionBFS()
solution_brutal = SolutionBrutal()

cases = [
    [4, [[1,0],[1,2],[1,3]]],
    [6, [[3,0],[3,1],[3,2],[3,4],[5,4]]],
    [3, [[0,1], [1,2]]],
    [4, [[1,0], [1,2], [1,3]]],
    [2, [[0,1]]],
    [1, []],
    # [7, [[0,2],[1,2],[1,3],[2,4],[3,5],[4,6]]]
]

for n, edges in cases:
    result1 =  solution.findMinHeightTrees(n, edges)
    result2 = solution_brutal.findMinHeightTrees(n, edges)
    if result1 != result2:
        print('input:', n, edges)
        print('result1:', result1)
        print('result2:', result2)









